class Solution {
public:
    int minSetSize(vector<int>& arr) {
        // 时间复杂度：O(nlogn)，其中 n 是 arr 的长度，瓶颈在排序上
        // 空间复杂度：O(n)
        // 用哈希表（或者数组）统计每个元素的出现次数
        // 哈希表写法
        // unordered_map<int, int> hash;
        // int n = arr.size() / 2;
        // for(int &x : arr)
        //     hash[x]++;

        // // 把出现次数从大到小排序，得到 t 数组
        // vector<int> t;
        // for(auto &e : hash)
        //     t.push_back(e.second);

        // sort(t.begin(), t.end());

        // // 遍历 t 数组，计算前缀和 s，直到 sum ≥ n即可，这里 n 上面已经算出来是数组大小的一半 
        // int ret = 0, sum = 0;
        // for(int i = t.size() - 1; i >= 0; i--)
        // {
        //     sum += t[i];
        //     ret++;
        //     if(sum >= n)
        //         return ret;
        // }
        // return ret;

        // 数组写法
        int mx = ranges::max(arr);
        vector<int> cnt(mx + 1);
        for(int &x : arr)
            cnt[x]++;

        ranges::sort(cnt, greater());   // 从大到小排序(从小到大贪心)

        int s = 0;
        for(int i = 0; ; i++)
        {
            s += cnt[i];
            if(s >= arr.size() / 2)
                return i + 1;
        }
        return -1;
    }
};